578C - Weakness and Poorness - CodeForces Solution

// :)

#include <bits/stdc++.h>
     
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
     
     
//-----------------debug--------------------------
vector<string> vec_splitter(string s) {
	s += ',';
	vector<string> res;
	while(!s.empty()) {
		res.push_back(s.substr(0, s.find(',')));
		s = s.substr(s.find(',') + 1);
	}
	return res;
}
void debug_out(
vector<string> __attribute__ ((unused)) args,
__attribute__ ((unused)) int idx, 
__attribute__ ((unused)) int LINE_NUM) { cerr << endl; } 
template <typename Head, typename... Tail>
void debug_out(vector<string> args, int idx, int LINE_NUM, Head H, Tail... T) {
	if(idx > 0) cerr << ", "; else cerr << "Line(" << LINE_NUM << ") ";
	stringstream ss; ss << H;
	cerr << args[idx] << " = " << ss.str();
	debug_out(args, idx + 1, LINE_NUM, T...);
}
#define deb(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
 
 
template <class T1, class T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
  return os << '{' << p.first << ", " << p.second << '}';
}
 
template <class T, class = decay_t<decltype(*begin(declval<T>()))>,
          class = enable_if_t<!is_same<T, string>::value>>
ostream &operator<<(ostream &os, const T &c) {
  os << '[';
  for (auto it = c.begin(); it != c.end(); ++it)
    os << &", "[2 * (it == c.begin())] << *it;
  return os << ']';
}
//support up to 5 args
#define _NTH_ARG(_1, _2, _3, _4, _5, _6, N, ...) N
#define _FE_0(_CALL, ...)
#define _FE_1(_CALL, x) _CALL(x)
#define _FE_2(_CALL, x, ...) _CALL(x) _FE_1(_CALL, __VA_ARGS__)
#define _FE_3(_CALL, x, ...) _CALL(x) _FE_2(_CALL, __VA_ARGS__)
#define _FE_4(_CALL, x, ...) _CALL(x) _FE_3(_CALL, __VA_ARGS__)
#define _FE_5(_CALL, x, ...) _CALL(x) _FE_4(_CALL, __VA_ARGS__)
#define FOR_EACH_MACRO(MACRO, ...)                                             \
  _NTH_ARG(dummy, ##__VA_ARGS__, _FE_5, _FE_4, _FE_3, _FE_2, _FE_1, _FE_0)     \
  (MACRO, ##__VA_ARGS__)
//Change output format here
#define out(x) #x " = " << x << "; "
#define debug(...)                                                              \
  cerr << "Line " << __LINE__ << ": " FOR_EACH_MACRO(out, __VA_ARGS__) << endl
//----------------------------------------------
 
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define FIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define SP fixed << setprecision(10)
     
//FILE *fin = freopen("in","r",stdin);
//FILE *fout = freopen("out","w",stdout);
     
const ll mod = 998244353;
const ll oo = 1e18;
const ll N = 1e5*4 + 10;

ll n, m, k;

ld ps[N], ans, a[N];
int f(ld x){
  ld mn = 0, mx = 0;
  ld re_mn = 0, re_mx = 0;
  for(int i = 1; i <= n; i++){
    ps[i] = ps[i-1]+a[i]+x;
    mn = min(mn, ps[i]);
    mx = max(mx, ps[i]);
    re_mn = min(re_mn, ps[i]-mx);
    re_mx = max(re_mx, ps[i]-mn);
    //deb(i, ps[i], mn, mx, re_mn, re_mx);
  }
  //if(max(abs(re_mx), abs(re_mx)) < ans) deb(x);
  ans = min(max(abs(re_mn), abs(re_mx)), ans);
  return abs(re_mn) < abs(re_mx);
}

ll lg = 100;
void code(){
  ans = oo;
  ld l = -1e5, r = 1e5;
  //f(-2);
  for(int t=0; t<lg; t++){
    ld md = (l+r)/2;
    ll s = f(md);
    if(s) r = md;
    else l = md;
  }
  cout<< SP<< ans<<"\n";
}
int main(){
  FIO;
  cin>> n;
  for(int i = 1; i <= n; i++ ) cin>> a[i];
  code();
}